As a hardware-directed algorithm for an elementary function operation, such as a trigonometric function, a CORDIC (COordinate Rotation Digital Computer) algorithm is known. The CORDIC algorithm is an iterative solving method that takes a function as vector rotation on a two-dimensional plane, and finds a true value by iteratively computing vector rotation of a predetermined basic rotational angle.
In the CORDIC algorithm, by selecting a rotational coordinate system (linear, circular, or hyperbolic), and by repeating a simple operation of a shift, addition, subtraction and table look-up, multiplication and division, trigonometric function computations, exponential and logarithmic computations, and hyperbolic function computations and the like can be executed, and the algorithm is widely used in digital signal processing fields.
Taking circular polar coordinates as an example, a j-th rotation process is represented by Expression (1).x(j+1)=x(j)+σj2−jy(j)y(j+1)=y(j)−σj2−jx(j)z(j+1)=z(j)+σjαj αj=arctan(2−j)j=0,1, . . . ,n−1  (1)
Here, n is the number of iterations.
Furthermore,σjε{1,−1}is a rotation direction parameter.
A vector [x(n), y(n)]′ implementing a rotation of a rotational angle θ with respect to a vector [x(0), y(0)]′ is represented by Expressions (2) and (3).
                              [                                                                      x                  ⁡                                      (                    n                    )                                                                                                                        y                  ⁡                                      (                    n                    )                                                                                ]                =                                            1                              K                n                                      ⁡                          [                                                                                          cos                      ⁢                                                                                          ⁢                      θ                                                                                                  sin                      ⁢                                                                                          ⁢                      θ                                                                                                                                                          -                        sin                                            ⁢                                                                                          ⁢                      θ                                                                                                  cos                      ⁢                                                                                          ⁢                      θ                                                                                  ]                                ⁡                      [                                                                                x                    ⁡                                          (                      0                      )                                                                                                                                        y                    ⁡                                          (                      0                      )                                                                                            ]                                              (        2        )                                          K          n                =                  1          /                                    ∏                              j                =                0                                            n                -                1                                      ⁢                                                  ⁢                                          1                +                                  2                                                            -                      2                                        ⁢                    j                                                                                                          (        3        )            
Here, Kn is a scaling coefficient.
Rotation according to the CORDIC algorithm is pseudo-rotation that accompanies scaling. In order to correct the scaling, it is necessary to perform processing indicated in Expression (4).
                              [                                                    xf                                                                    yf                                              ]                =                              K            n                    ⁡                      [                                                                                x                    ⁡                                          (                      n                      )                                                                                                                                        y                    ⁡                                          (                      n                      )                                                                                            ]                                              (        4        )            
As indicated in Expression (5), the CORDIC algorithm realizes a rotation operation of the rotational angle θ as a combination of basic rotation of angle αj.
                    θ        =                              ∑                          j              =              0                                      n              -              1                                ⁢                                    σ              j                        ⁢                          α              j                                                          (        5        )            
The CORDIC algorithm has 2 modes: a Rotation mode and a Vector mode, according to a method of determining the rotation direction parameter σj given in Expression (6).
                              σ          j                =                  {                                                                      sign                  ⁢                                                                          ⁢                                      (                                          z                      ⁡                                              (                        j                        )                                                              )                                    ⁢                                      (                    Rotation                    )                                                                                                                        sign                  ⁢                                                                          ⁢                                      (                                          y                      ⁡                                              (                        j                        )                                                              )                                    ⁢                                      (                    Vectoring                    )                                                                                                          (        6        )            
In the Rotation mode, with a desired angle θ as z(0), processing is performed to rotate, by an amount θ, an initial vector [x(0), y(0)]′.
In the Vector mode, with an initial angle z(0) as 0, a process is performed to rotate the vector up to an x axis, and to obtain a rotational angle (z(n)) thereof and the norm (x(n)) of the initial vector.
Since the CORDIC algorithm implements the rotation process by n basic rotations, essentially a rotational angle error less than a final basic rotational angle αn−1 occurs.
In order that Expression (7) holds with n bit accuracy (refer to Non-Patent Document 1), the CORDIC algorithm must perform iterative processing of the same number of steps as the required bit accuracy.αj=arctan(2−j)=2−j(j>n/3)  (7)
When the CORDIC algorithm is implemented, in addition to the rotational angle error, it is necessary to take into account a rounding error that accompanies the shift addition and subtraction.
It is known that if bit width b of a data path satisfies Expression (8), an output value of n bit accuracy is obtained. Details thereof may be referred to in the descriptions of Non-Patent Documents 1 and 2.b=g+n+m g=2m=log 2(n)  (8)
where, g is the number of MSB (Most Significant Bit) guard bits for an overflow strategy, and in is the number of LSB (Least Significant Bit) guard bits in a rounding error strategy.
Since the CORDIC algorithm requires an iterative structure with the same number of stages as the required bit accuracy, it is difficult to realize speeding up using a parallel structure as seen in a multiplier.
In order to solve this problem, a linear approximation CORDIC algorithm is proposed. The linear approximation CORDIC algorithm (Rotation mode), similar to the original algorithm, performs iterative processing as indicated by Expression (1) from j=0 to n/2.
Next, instead of iterative processing from j=n/2+1 to n−1, processing as indicated in Expression (9) is performed. Here, q=j/2. The process of the Expression (9) utilizes the fact thatarctan(z(q))can be linearly approximated byz(q)and this is the origin of the name of “linear approximation CORDIC”.
                              [                                                                      x                  ⁡                                      (                    n                    )                                                                                                                        y                  ⁡                                      (                    n                    )                                                                                ]                =                  [                                                                                          x                    ⁡                                          (                      q                      )                                                        +                                                            z                      ⁡                                              (                        q                        )                                                              ⁢                                          y                      ⁡                                              (                        q                        )                                                                                                                                                                                      y                    ⁡                                          (                      q                      )                                                        -                                                            z                      ⁡                                              (                        q                        )                                                              ⁢                                          x                      ⁡                                              (                        q                        )                                                                                                                          ]                                    (        9        )            
Finally, scale correction as indicated by Expression (10) is performed.
                                          [                                                            xf                                                                              yf                                                      ]                    =                                    K              q                        ⁡                          [                                                                                          x                      ⁡                                              (                        n                        )                                                                                                                                                        y                      ⁡                                              (                        n                        )                                                                                                        ]                                      ⁢                                  ⁢                              K            q                    =                      1            /                                          ∏                                  j                  =                  0                                q                            ⁢                                                          ⁢                                                1                  +                                      2                                                                  -                        2                                            ⁢                      j                                                                                                                              (        10        )            
The linear approximation CORDIC shortens processing delay by performing multiplication in which speeding up is possible using a parallel structure, instead of shift addition/subtraction iterative processing in a later stage of the original CORDIC algorithm.
FIG. 3 is a diagram showing a typical structure of a linear approximation CORDIC circuit (Rotation mode) in first related technology. The first related technology as in FIG. 3, is referred to in the description of Non-Patent Document 1. It is to be noted that in the present document, the description below concerns Rotation mode, as long as it is not particularly stated otherwise.
The linear approximation CORDIC circuit 1001 includes:
first to q-th rotation processing circuits 1001-100q,
X and Y path constant multipliers 200x and 200y, 
X and Y path variable multipliers 300x and 300y, and
X and Y path adder/subtractors 400x and 400y. 
The first to q-th rotation processing circuits 1001-100q perform iterative processing from j=0 to q (=n/2), as indicated by Expression (1), with respect to initial values x(0), y(0), and z(0) to output x(q), y(q), and z(q).
Here, n is required bit accuracy.
Signals x(j), y(j), and z(j) are all of b bit width.
Here, b is expressed by Expression (8).
The X and Y path variable multipliers 300x and 300y, and the X and Y path adder/subtractors 400x and 400y perform processing as indicated by Expression (9), to output x(n) and y(n) of b bit width.
The X and Y path variable multipliers 300x and 300y utilizes the fact thatz[q]<2−q to extract only effective upper (n/2+m) bits of x(q), y(q), and z(q), and perform (n/2+m)×(n/2+m) bit variable multiplication.
The X and Y path constant multipliers 200x and 200y perform multiplication by a constant Kq on x(n) and y(n), perform scaling processing as indicated by Expression (10), and output scaling results xf and yf of b bit width to the outside.
Since Kq must be less than 1, the MSB guard bits g are unnecessary, and since the following expression may hold:ct=b−g=n+m bitsthe X and Y path constant multipliers 200x and 200y perform (ct)×b bit constant multiplication.
With regard to the linear approximation CORDIC circuit 1001 of the first related technology, a method of further shortening the processing delay is proposed.
FIG. 4 is a diagram showing a configuration of a linear approximation CORDIC circuit in second related technology. Details of the second related technology are also described in Non-Patent Document 1.
The linear approximation CORDIC circuit 1002 of the second related technology is provided with:
first to q-th rotation processing circuits 1001-100q,
X and Y path constant multipliers 200x and 200y, 
X and Y path variable multipliers 300x and 300y, 
X and Y path adder/subtractors 400x and 400y, and
a Z path constant multiplier 500.
In the linear approximation CORDIC circuit 1002 of the second related technology, in contrast to the linear approximation COMIC circuit 1001 of the first related technology, the Z path constant multiplier 500 is added, and the placements of the X and Y path constant multipliers 200x and 200y are moved to a stage before the X and Y path adder/subtractors 400x and 400y, respectively. Elements other than this are the same as those in FIG. 3.
The linear approximation CORDIC circuit 1002 of the second related technology, similar to the first related technology, performs iterative processing by the rotation processing circuits 1001 and 100q, and obtains x(q), y(q), and z(q).
The Z path constant multiplier 500 performs scaling processing on z(q), as indicated by Expression (11).P=Kqz(q)  (11)
Next, processing as indicated in Expression (12) is performed.
                              [                                                    xf                                                                    yf                                              ]                =                  [                                                                                                                K                      q                                        ⁢                                          x                      ⁡                                              (                        q                        )                                                                              +                                      Py                    ⁡                                          (                      q                      )                                                                                                                                                                                      K                      q                                        ⁢                                          y                      ⁡                                              (                        q                        )                                                                              -                                      Px                    ⁡                                          (                      q                      )                                                                                                    ]                                    (        12        )            
Specifically, in the X and Y path constant multipliers 200x and 200y, and the X and Y path variable multipliers 300x and 300y, x(q) and y(q) are multiplied by Kq and P, and using the X and Y path adder/subtractors 400x and 400y, multiplied results are added or subtracted, and xf and yf are obtained and outputted to the outside.
Since z(j) (j>n/3) can be obtained at high speed by Recoding processing utilizing the fact that Expression (7) holds, x(q) and y(q) form critical paths, even when the Z path constant multiplier 500 is added.
Details of the Recoding processing are described in Non-Patent Document 1 and a description is omitted.
In the linear approximation CORDIC circuit 1002 of the second related technology, processing of the X and Y path constant multipliers 200x and 200y, and the X and Y path variable multipliers 300x and 300y can be carried out in parallel, and since scaling processing in a later stage of the X and Y path adder/subtractors 400x and 400y is unnecessary, there is an advantage in that it is possible to shorten the processing delay, in comparison with the linear approximation CORDIC circuit 1001 of the first related technology. However, it is necessary to add the Z path constant multiplier 500, so that the circuit scale becomes large.
[Non-Patent Document 1]
    Antelo, E. Villalba, J., “Low latency pipelined circular CORDIC” Computer Arithmetic 2005. ARITH-17 2005. Proceedings of 17th IEEE Symposium on Computer Arithmetic, pp. 280-287 June 2005.[Non-Patent Document 2]    Y H Hu, “The quantization effects of the CORDIC algorithm” IEEE Transactions on Signal Processing 40:44, 834-844 pp. 1822-1825, 1988.[Non-Patent Document 3]    E. F. Deprettere, P. Dewilde, and R. Udo, “Pipelined CORDIC architectures for fast VLSI filtering and array processing,” in Proceedings IEEE ICASSP, pp. 41A.6.1-41A.6.4, March 1984.